The present invention relates to a method of compressing a data to be compressed such as a test pattern used for testing, for example, a semiconductor integrated circuit (IC), a method of expanding such data, an apparatus for compressing such data, and an apparatus for expanding such data. In addition, the present invention relates to a compressing method, an expanding method, a compressing apparatus and an expanding apparatus for compressing and expanding a test pattern used for testing a large scale semiconductor integrated circuit (LSI) by each pin basis of a large scale semiconductor integrated circuit (hereinafter referred to as LSI).
In an IC testing apparatus (commonly called IC tester) for testing a semiconductor integrated circuit (hereinafter referred to as IC), the data quantity or volume of test patterns applied to an IC to be tested (IC under test) becomes extensive. Therefore, the extensive test pattern data are compressed to be transmitted and the compressed test pattern data are expanded at a receiving side to reconstruct original test pattern data which are applied to an IC under test. As a method for compressing test patterns or other extensive data, a Lempel Ziv""s algorithm (LZ compressing method) which utilizes a dictionary, a Huffman""s algorithm (Huffman compressing method) which utilizes statistical characteristics of the data, or variations of those various compressing methods have conventionally been used in a data compressing apparatus. Each of those compressing methods is a single compressing method and each of the data compressing apparatus applies this single compressing method to all the data to be compressed to perform the compression of those data.
However, since each data such as a test pattern has a uniform data type and is composed of a plurality of unit data sequences but a considerably different data structure or a statistical characteristic from each other, an efficient compression has not been possible depending on the data to be used. For example, when each of different portions within a same data is significantly different from each other in terms of the pattern structure or the statistical characteristic, a high compression efficiency can be obtainable for a certain portion but the compression efficiency becomes low for remaining portions. As a result, the compression rate is relatively low for the entire data. In addition, regarding the processing time, since the processing time is different depending on the structure of a data, an optimum processing time has not been attained.
There has been proposed, from this stand point, a data compression wherein a test pattern is divided into blocks each having a different data structure or a statistical characteristic from the others and an appropriate compressing method is applied to each block to compress the data.
However, since, in this data compressing method, the test pattern to be compressed is compressed in a block basis, it is required that the data expansion is also performed in a block basis. Therefore, it is impossible, in this compressing method, to expand the compressed test pattern in a real time basis.
Further, talking about the microprocessors produced by Intel Corporation as example, the number of pins has increased year by year as the integration degree is improved as seen in the models 4004 in 1971 having 16 pins, 80286 in 1982 having 68 pins, 80386 in 1985 having 132 pins, 80486 in 1989 having 168 pins, Pentium in 1993 having 296 pins, and Pentium Pro. in 1995 having 387 pins. As a result, an automatic IC test system (ATE) has also been shifted to a system wherein the hardware of a testing apparatus corresponds to a pin (per-pin system). This is because, with the per-pin architecture, the automatic IC testing system can flexibly cope with the increasing number of pins.
In order to solve the test pattern problems described above, there are required a per-pin compressing apparatus and a per-pin expanding apparatus wherein a test pattern is handled in the state that the test pattern is divided into a plurality of data each corresponding to a pin. The per-pin architecture has advantages such as (a) since the test data each corresponding to each pin can be down loaded into an internal memory of an automatic test system at the same time, the down loading time of a compressed test pattern can be reduced, (b) since management of the compressing apparatus and the expanding apparatus is simplified, the automatic test system can flexibly cope with increase of the number of pins of an IC.
A conventional automatic IC testing system (hereinafter referred to as ATE) holds therein a test pattern for testing an IC in a pattern generator. Therefore, in the ATE, a very long time is required for down loading a test pattern from a disk drive storing the test pattern therein to a pattern generator of the ATE. For example, approximately one hour is required, in case of a down loading via a network, for down loading a test pattern having approximately one (1) G bytes (giga bytes). Therefore, it is a serious problem to be solved to decrease the down loading time and to improve an availability factor of the ATE.
It is an object of the present invention to provide a data compressing method wherein the data to be compressed having data portions, which are called hereinafter as unit data sequences and each of which has a different structure or a different statistical characteristic is divided into the unit data sequences which are distributed into a plurality of blocks each corresponding to one of those factors of data structure and structural characteristics of data and the unit data sequences distributed to the respective blocks can efficiently be compressed by applying optimum compressing methods to the respective blocks.
It is another object of the present invention to provide a data expanding method wherein the respective data sequences divided into a plurality of blocks and compressed can be expanded and reconstructed to the original data without any information loss.
It is still another object of the present invention to provide a test pattern compressing method and a test pattern compressing apparatus wherein a test pattern is divided into test sequences each corresponding to each pin of a semiconductor integrated circuit and the test pattern to be compressed can efficiently be compressed by measuring the structure or the statistical characteristic of the data to apply an optimum compressing method to each test sequence.
It is still another object of the present invention to provide a test pattern expanding method and a test pattern expanding apparatus wherein respective test sequences for each pin of a semiconductor integrated circuit compressed by the above compressing method or compressing apparatus can be expanded to the original test pattern data in real time basis for each pin without any information loss.
It is yet still another object of the present invention to provide a test pattern compressing method and a test pattern expanding method wherein data sequences divided into a plurality of blocks is compressed by applying an optimum compressing method to each of the blocks and the compressed data divided into those plurality of blocks can be reconstructed to the original data from the respective blocks without any information loss.
It is yet still another object of the present invention to provide an automatic test system of a semiconductor integrated circuit wherein a down loading time of a test pattern is reduced using the test pattern compressing apparatus and/or the test pattern expanding apparatus.
The data compressing method according to the present invention is characterized in that in a compressing method wherein an input data having a redundancy, for example, a test pattern data, is divided into test sequences and compressed in each pin basis of a semiconductor integrated circuit, the data compressing method comprises the steps of: dividing each input data into a plurality of data portions, namely unit data sequences, to distribute each portion to one of blocks in accordance with at least one one of factors of the data structure or the statistical characteristic of the data; and applying an appropriate compressing method to each of the blocks; whereby a proper compression can be obtained for all the data.
The data expanding method according to the present invention comprises the steps of: dividing the input compressed data from data compressing step according to any preceding data compressing method into a plurality of compressed unit data sequences and distributing them into a plurality of blocks in accordance with the structure of the compressed data; and applying an appropriate expanding method to each of the blocks; whereby the compressed data can be reconstructed to the original data without any information loss.
In a datacompressing method of a preferred embodiment, the dividing step includes the steps of: calculating a threshold value of the number of data changes for dividing the input data into unit data sequences; counting the number of data changes of each the divided unit data sequence of the input data; comparing the actual number of data changes with the threshold value; and distributing a divided unit data sequence to one of the plurality of blocks in accordance with the comparison result; whereby the input data can be divided into proper blocks.
In the data compressing method of another preferred embodiment, the dividing step includes the step of: calculating a threshold value of entropy for dividing the input data into blocks; measuring an appearing probability of each symbol in the input data to calculate a data entropy from the appearing probabilities of symbols; comparing an actual data entropy with the threshold value; and distributing a divided data portion to one of the plurality of blocks in accordance with the comparison result; whereby the input data can be divided into proper blocks.
In the data compressing method of still preferred another embodiment, the dividing step is a step wherein the number of data changes is counted for the input data and the input data is divided into blocks in accordance with the number of data changes; a run length compressing method is applied, in the step of applying the appropriate compressing method, to a block having smaller number of data changes than the threshold value; and respective proper compressing methods are applied to the other blocks; whereby a proper compression can be obtained for all the data.
In a data expanding method of a preferred embodiment, the dividing step for expanding the compressed data is characterized in that the compressed data is divided into a data block of compressed unit sequences compressed by the run length compressing method and a data block of compressed unit data sequences compressed by the other plurality of compressing methods and the divided compressed unit data sequences compressed by the run length compressing method are expanded by a run length expanding method in the step of applying the appropriate expanding method; whereby the compressed data is reconstructed to the original data without any information loss.
In the data expanding method of still preferred another embodiment, the data expanding method is characterized in that there is included therein a step for performing Burrows Wheeler transform (hereinafter referred to as BW transform) at least once for the block divided in the dividing step and having high periodicity data; the run length compressing method is applied, in the compressing step, to the data transformed by BW transform; and respective appropriate compressing methods are applied to the other blocks; whereby a proper compression is obtained for all the data.
In the data expanding method of preferred another embodiment, the dividing step for expanding a compressed data is characterized in that the compressed data is divided into unit data sequence compressed by the run length compressing method after the compressed data is transformed by BW transform and unit data sequences compressed by the other compressing methods; the unit data sequence compressed by the run length compressing method after BW transform is applied is expanded by the run length expanding method in the step of applying an appropriate expanding method and thereafter, inverse BW transform is applied to the unit data sequence compressed by the run length compressing method by the number of application times of the BW transform; whereby the compressed data is reconstructed to the original data without any information loss.
In the data compressing method of still preferred another embodiment, the data compressing method is characterized in that a Huffman compressing method is applied, in the step for applying an appropriate compressing method, to the block having an entropy smaller than a threshold value among the blocks divided in the dividing step and respective appropriate compressing methods are applied to the other blocks: whereby a proper compression can be obtained for all the data.
In the data expanding method of still preferred another embodiment, the data expanding method is characterized in that a compressed data is divided into unit data sequences compressed by the Huffman compressing method and unit data sequences compressed by the other compressing methods; and a Huffman expanding method is applied, in the step of applying an appropriate expanding method, to the unit data sequences compressed by the Huffman compressing method; whereby the data can be reconstructed to the original data without any information loss.
In the data compressing method of still preferred another embodiment, the data compressing method is characterized in that an LZ compressing method is applied, in the step of applying an appropriate compressing method, to the block having a small entropy among the divided blocks; and respective optimum compressing methods are applied to the other blocks; whereby a proper compression can be obtained for all the data.
In the data expanding method of still preferred another embodiment, the data expanding method is characterized in that a compressed data is divided into unit data sequences compressed by the LZ compressing method and unit data sequences compressed by the other compressing methods; and an LZ expanding method is applied, in the step of applying an appropriate expanding method, to the unit data sequences compressed by the LZ compressing method; whereby the compressed data can be reconstructed to the original data without any information loss.
In the data compressing method of still preferred another embodiment, the data compressing method is characterized in that an arithmetic coding compressing method is applied, in the step of applying an appropriate compressing method, to the block having a small entropy among the divided blocks; and respective appropriate compressing methods are applied to the other blocks; whereby an optimum compression can be obtained for all the data.
In the data expanding method of still preferred another embodiment, the data expanding method is characterized in that the compressed data is divided, in the dividing step, into data compressed by an arithmetic coding compressing method and data compressed by the other compressing methods; and an arithmetic coding expanding method is applied, in the step of applying an appropriate expanding method, to the data compressed by the arithmetic coding compressing method; whereby the compressed data can be reconstructed to the original data without any information loss.
In the data compressing method of still preferred another embodiment, the dividing step includes the steps of: inputting environmental parameters for a proper block division; and calculating a threshold value of the number of data changes for the block division using the inputted environmental parameters; whereby an optimum block division can be performed.
In the data compressing method of still preferred another embodiment, the dividing step includes the steps of inputting environmental parameters for an appropriate block division, and using the inputted environmental parameters to calculate a threshold value of an entropy for a block division.
In the data compressing method of still preferred another embodiment, the data compressing method includes the steps of calculating a threshold value of the number of data changes for a data division, and using the calculated threshold value to estimate a compression rate of the inputted data and to optimize the threshold value so that the compression rate is maximized, whereby an optimum block division can be made possible using the optimized threshold value in the dividing step.
In the data compressing method of still preferred embodiment, the data compressing method is characterized in that the data compressing method comprises the steps of calculating a threshold value of entropy for a data division, and using the calculated threshold value to estimate a compression rate of the inputted data and to optimize the threshold value so that the compression rate is maximized, and in that the optimized threshold value is used in the dividing step, whereby an optimum block division can be made possible.
A test pattern compressing apparatus according to the present invention is characterized in that the test pattern compressing apparatus comprises dividing means for dividing an inputted test pattern into test sequences each corresponding to a pin of an integrated circuit under test, and test sequence compressing means for selecting an appropriate compressing method in accordance with a data structure of each test sequence to compress the test sequence for each pin, whereby the maximum compression rate for all the data can be obtained. In this test pattern compressing apparatus, a test pattern is inputted thereto and data each being compressed in a pin basis can be collectively outputted or can be outputted in the sequence of compression.
In the test pattern compressing method of further preferred another embodiment, the test pattern compressing method comprises the steps of dividing an inputted test pattern into test sequences each corresponding to a pin of an integrated circuit under test, and selecting an appropriate compressing method in accordance with a data structure of each test sequence to compress the test sequence for each pin.
In the test pattern compressing apparatus of further preferred another embodiment, the test sequence compressing means is provided for each pin, and those test sequence compressing means operate in parallel to output compressed data in parallel.
In the test pattern compressing method of still preferred another embodiment, the compressing steps are performed in parallel for respective test sequences divided in pin basis. A high speed and highly efficient compression can be obtained.
The test pattern expanding apparatus according to the present invention comprises compressed data dividing means for dividing an inputted compressed data into compressed data each corresponding to each pin of an integrated circuit under test, and test sequence expanding means for selecting an appropriate expanding method in accordance with a flag indicating a compressing method for each divided compressed data and for applying the selected expanding method thereto.
In the test pattern expanding method of still preferred another embodiment, the test pattern expanding method comprises the steps of dividing an inputted compressed data into compressed data each corresponding to each pin of an integrated circuit under test, and selecting an appropriate expanding method in accordance with a flag indicating a compressing method for each divided compressed data and applying the selected expanding method thereto.
The test pattern expanding apparatus according to the present invention is characterized in that the test pattern expanding apparatus comprises the test sequence expanding means each being for each pin and those test sequence expanding means operate in parallel.
In the test pattern expanding method of further preferred another embodiment, the expanding steps are performed in parallel in respective pin basis.
The test sequence compressing means in the test pattern compressing apparatus according to the present invention comprises compressing method determining means for determining a proper compressing method adapted for an inputted test sequence, run length compressing means for compressing a test sequence using a run length compressing method, and BWT run length compressing means for applying a run length compression after applying BW transform at least once to the test sequence.
This test pattern compressing apparatus also includes, as compressing means, means for using an LZ compressing method, a Huffman compressing method, an arithmetic coding compressing method, and the like as compressing means of further other compressing methods.
The test pattern compressing method according to the present invention comprises, in the test sequence compressing step, the steps of determining a proper compressing method to be applied to an inputted test sequence, and applying the run length compressing method or applying the run length compressing method after applying BW transform one or more times (herein after referred to as a BWT run length compressing method), or applying any one of the other compressing methods (an LZ compressing method, a Huffman compressing method, an arithmetic coding compressing method and the like) to a test sequence to perform a compression of the test sequence.
The test sequence expanding apparatus in the test pattern expanding apparatus according to the present invention comprises compressing method determining means for determining whether a compressed data is a data compressed by the run length compressing method, a data compressed by the BWT run length compressing method or a data compressed by one of the other compressing methods such as the LZ compressing method, run length expanding means for performing an expansion of the compressed data using the run length expanding method, repetitive inverse BW transform means for applying inverse BW transform at least once to a data expanded by the run length expanding means to perform a data transform, and other expanding means for performing expansions of the compressed data using expanding methods corresponding to the other compressing methods.
The test pattern expanding method according to the present invention comprises the steps of determining, in the step of expanding the test sequence, whether a compressed data is a data compressed by the run length compressing method, a data compressed by the BWT run length compressing method or a data compressed by one of the other compressing methods such as the LZ compressing method, and selecting a proper expanding method corresponding to the compressing method for the compressed data to apply the selected expanding method to the compressed data.
The compressing method determining means in the test pattern compressing apparatus according to the present invention comprises BW transform optimizing means for calculating the proper number of times which is appropriate for applying BW transform to a test sequence, threshold value storage means for storing a threshold value of compression rate, compression rate comparator means for comparing the maximum value of compression rate obtained by the BW transform optimizing means with the threshold value stored in the threshold value storage means, and compressing method selecting means for selecting, in accordance with a comparison result obtained by the compression rate comparator means and the optimum number of times of applying BW transform obtained by the BW transform optimizing means, as to whether the test sequence should be compressed by the run length compressing method, by the BWT run length compressing method, or one of the other compressing methods such as LZ compressing method.
The BW transform optimizing means in the compressing method determining means comprises the steps of applying BW transform to a test sequence, measuring the number of data changes of a transformed data by applying BW transform, calculating a compression rate from the number of data changes, and obtaining the maximum value of compression rate and the number of application times of BW transform at which the compression rate is maximized.
A semiconductor integrated circuit automatic test system using the test pattern compressing apparatus and the test pattern expanding apparatus according to the present invention has a large capacity storage device (for example, a disk drive) for storing compressed test pattern data, a pattern generator for storing test pattern data and for generating test patterns, and test pattern expanding means for completely reconstructing the compressed test pattern data to the original test pattern without any information loss, whereby a test pattern down loading time can be reduced.
The semiconductor integrated circuit automatic test system comprises a large capacity storage device (for example, a disk drive) for storing compressed test pattern data, a pattern generator for storing the test pattern data and generating test patterns, and a plurality of test sequence expanding means each for completely reconstructing a test sequence data compressed in each pin basis to an original test pattern in parallel for respective pins without any information loss.